package progect_01;

import java.security.KeyStore.Entry;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import javax.swing.event.ListDataListener;

public class HuffTreeZip {
	public static Map<Character, String> huffmancodesMap=new TreeMap<Character, String>();
	public static StringBuilder stringBuilder=new StringBuilder();
	public static StringBuilder StrTurnCharResult=new StringBuilder();
	public static void main(String[] args) {
		String str="i like like like java do you like a java";//40
		//用于存放统计的不同字符个数
		Map<Character,Integer> dataMap=new HashMap<Character, Integer>();
		dataMap=CountWord(str,dataMap);
		ArrayList<HuffmanNode> nodes=new ArrayList<>();//用于存放转换后的结点
		nodes=TurnHuffNode(dataMap, nodes);
		//创建哈夫曼树
		HuffmanNode root=CreteHuffTree(nodes);
		//遍历哈夫曼树
		//PreOrder(root);
		//数据压缩
		Map<Character, String> map=HuffmanTreeZip(root);
		
		//将要处理的字符串转为对应的字节--133总长
		TurnStrToByte(str);
		CodeByte();
		//获取最终转换后的字节数组
		byte[] finCodes=CodeByte();
		

	}
	
	//将处理后的字节133位每8位放在一起,并转成10进制
	public static byte[] CodeByte() {
		byte[] finCodes;
		ArrayList<String> list=new ArrayList<String>();
		int len=StrTurnCharResult.length();//133
		int n=0;
		for(int i=0;i<len;i=i+8) {// 12345678 12345678 123-->19
			                      //第一次截取：(0,8) 二次(8,16) 三次：(16,19)
			if(i+8<len) {
				list.add(StrTurnCharResult.toString().substring(i, i+8));
			}else {
				//说明最后一组不满8位
				list.add(StrTurnCharResult.toString().substring(i,len));
			}
		}
		//将每8位都转为一个byte类型放到字节数组中
		finCodes=new byte[list.size()];
		for(int i=0;i<list.size();i++) {
			finCodes[i]=(byte)Integer.parseInt(list.get(i));
		}
		return finCodes;
		
	}
	
	
	
	
	
	//将要处理的字符串转为各个字符对应的二进制数组
	public static void TurnStrToByte(String str) {
		
		//首先根据字符串的每一位找到map集合中对应的字节
		for(int i=0;i<str.length();i++) {
			char data=str.charAt(i);
			for(Map.Entry<Character, String> entry:huffmancodesMap.entrySet()) {
				Character key=entry.getKey();
				if(key.equals(data)) {
					StrTurnCharResult.append(entry.getValue());
				}
			}
			
		}
		
	}
	

	
	//数据压缩--要实现1、获取哈夫曼树的编码 2、根据根据生成哈夫曼编码实现上述字符串对应的编码
	
	public static  Map<Character,String> HuffmanTreeZip(HuffmanNode node) {
		if(node==null) {
			return null;
		}
		HuffDataZip(node.getLeft(), "0", stringBuilder);
		HuffDataZip(node.getRight(), "1", stringBuilder);
		return huffmancodesMap;
	}
	
	public static void HuffDataZip(HuffmanNode node,String code,StringBuilder stringBuilder) {
		StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
		stringBuilder2.append(code);
		if(node!=null) {
			if(node.getData()=='根') {
				//非叶子结点
				HuffDataZip(node.getLeft(), "0", stringBuilder2);
				HuffDataZip(node.getRight(), "1", stringBuilder2);
			}else {
				//此时找到了叶子结点--将上面字符所对应的编码添加上去
				huffmancodesMap.put(node.getData(), stringBuilder2.toString());
			}
		}
		
	}
	
	
	//前序遍历
	public static void PreOrder(HuffmanNode root) {
		if(root!=null) {
			root.PreOrder();
		}
		
	}
	//创建哈夫曼树
	public static HuffmanNode CreteHuffTree(ArrayList<HuffmanNode> nodes) {
		//最后把创建好的结点添加进去，最后一次添加的是根节点
		while(nodes.size()>1) {
			//先排序
			Collections.sort(nodes);
			//取出最小和次小
			HuffmanNode leftNode=nodes.get(0);
			HuffmanNode rightNode=nodes.get(1);
			//创建新的根节点
			HuffmanNode parentNode=new HuffmanNode('根',leftNode.getNum()+rightNode.getNum());
			
			//创建子树
			parentNode.setLeft(leftNode);
			parentNode.setRight(rightNode);
			//删除两个结点
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			//添加节点进去
			nodes.add(parentNode);
		}
		//返回根节点--最后一个元素
		return nodes.get(0);
		
	}
	
	
	//将这些数据转为结点
	public static ArrayList<HuffmanNode> TurnHuffNode(Map<Character, Integer> dataMap,ArrayList<HuffmanNode> nodes){
		for(Map.Entry<Character,Integer> entry:dataMap.entrySet()) {
			nodes.add(new HuffmanNode(entry.getKey(), entry.getValue()));
		}
		return nodes;
	}
	
	//统计每个字符的位数
	public static Map<Character, Integer> CountWord(String str,Map<Character, Integer> dataMap) {
		//键：字符，值：这个字符的出现次数
		
		for(int i=0;i<str.length();i++) {
			char DataKey=str.charAt(i);
			if(dataMap.containsKey(DataKey)) {
				//集合中要是已经存在这个字符的话，就将个数+1即可
				int count=dataMap.get(DataKey);
				dataMap.put(DataKey, ++count);	
			}else {
				//说明集合中还不存在这个字符，那么就添加这个字符，同时把个数变成1
				dataMap.put(DataKey, 1);
			}
		}
		return dataMap;
	}

}
class HuffmanNode implements Comparable<HuffmanNode>{
    private char data;
    private int num;
    private HuffmanNode left;
    private  HuffmanNode right;

    //构造器
    public HuffmanNode(char data,int num){
        this.data=data;
        this.num=num;
    }
  	
    
    //前序遍历
    public void PreOrder() {
    	System.out.println(this.getData()+" ,"+this.getNum());//this--》调用者
    	if(this.left!=null) {
    		this.left.PreOrder();
    	}
    	if(this.right!=null) {
    		this.right.PreOrder();
    	}
    }
    
    
    public char getData() {
        return data;
    }

    public void setData(char data) {
        this.data = data;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public HuffmanNode getLeft() {
        return left;
    }

    public void setLeft(HuffmanNode left) {
        this.left = left;
    }

    public HuffmanNode getRight() {
        return right;
    }

    public void setRight(HuffmanNode right) {
        this.right = right;
    }
    
    @Override
    public int compareTo(HuffmanNode o) {
    	// TODO Auto-generated method stub
    	return this.num-o.num;
    }
   
}